package com.lds.offer.demo;


import com.lds.offer.entity.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @description: Offer 54. 二叉搜索树的第k大节点
 * @author: lds
 * @create: 2022-10-07 13:58
 **/
public class Offer_54_二叉搜索树的第k大节点 {

    //https://leetcode.cn/problems/er-cha-sou-suo-shu-de-di-kda-jie-dian-lcof/

    /**
     * 二叉搜索树: 左<根<右
     * 由此可以知道中序遍历（左根右） 为递增的
     * 所以我们只需要将中序遍历倒序（右根左） 即为递减的
     * 最终第k大节点就可以转换为中序遍历倒序的第k个节点
     */

    public static int k = 1;
    public static int l = 1;
    public static int res;
    public static List<Integer> list = new ArrayList<>();


    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.init();
        //打印中序遍历倒序
        print(treeNode);
        System.out.println();
        //中序遍历倒序
        dfs(treeNode);
        System.out.println(res);
        //转换为集合方式
        arr(treeNode);
        System.out.println(list.get(l-1));
    }

    public static void dfs(TreeNode root) {
        if(root == null) return;
        dfs(root.right); // 右
        if (k == 0) return;
        k--;
        res = root.val;
        dfs(root.left); // 左
    }

    public static void arr(TreeNode node) {
        if (node == null) return;
        arr(node.right);
        list.add(node.val);
        arr(node.left);
    }

    public static void print(TreeNode node){
        if (node == null) return;
        print(node.right);
        System.out.print(node.val);
        print(node.left);
    }

}

